import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/29 15:14
 * @description 线段树 + 二分查找
 */
public class DinnerPlates {

    int c;
    /**
     * push的最多调用次数
     */
    int M = 2 * (int) 1e5 + 5;
    /**
     * 区间内的元素个数
     */
    int[] d = new int[M  * 4];
    Deque<Integer>[] deques;

    public DinnerPlates(int capacity) {
        c = capacity;
        deques = new Deque[M];
    }

    public void push(int val) {
        int left = 0, right = M;
        while (left < right) {
            int m = left + right >> 1;
            if (query(1, 0, M, 0, m) == (m + 1) * c) {
                // 如果满了，向下一个
                left = m + 1;
            }else {
                right = m;
            }
        }
        // 最终left下标为从左到右的第一个没有满的栈
        change(1, 0, M, left, 1);
        if (deques[left] == null) {
            deques[left] = new ArrayDeque<>();
        }
        deques[left].push(val);
    }

    public int pop() {
        int lo =  1, hi = M;
        while (lo < hi) {
            int m = lo + hi >> 1;
            // 从右往左，查找第一个非空栈
            if (query(1, 0, M, m, M) > 0) {
                lo = m + 1;
            }else {
                hi = m;
            }
        }
        if (deques[lo - 1].size() > 0) {
            int res = deques[lo - 1].pop();
            change(1, 0, M, lo - 1, -1);
            return res;
        }
        return -1;
    }

    public int popAtStack(int index) {
        if (deques[index].size() > 0) {
            int ans = deques[index].pop();
            change(1, 0, M, index, -1);
            return ans;
        }
        return -1;
    }

    int query(int p, int l , int r, int s, int t) {
        // 查询区间[s,t]内的元素个数, p为当前节点，[l, r]为当前节点的区间范围
        if (r < s || l > t) {
            return 0;
        }else if ( s <= l && r <= t) {
            // 当前区间为查询区间的子集
            return d[p];
        }else {
            int m = l + r >> 1;
            // 递归查询左右节点的元素个数，相加
            return query(p << 1, l , m , s, t) + query(p << 1 | 1, m + 1, r , s, t);
        }
    }

    void change(int p, int l, int r, int x, int v) {
        if (r < x || l > x) {
            return;
        }
        if (l == r ) {
            // 到达叶子节点，如果push，那么v = 1, 如果pop，那么v = -1.
            d[p] += v;
            return;
        }
        int m = (l + r) >> 1;
        change(p << 1, l, m, x, v);
        change(p << 1 | 1, m + 1, r, x, v);
        d[p] = d[p << 1] + d[p << 1 | 1];
    }
}
